package Algorithm.handleString;

import java.util.HashMap;

/**
 * 383. 赎金信 https://leetcode.cn/problems/ransom-note
 * 题目简述：判断字符串magazine中是否包含字符串ransomNote，每个字符只能用一次，字符串中都为小写字母
 */
public class CanConstruct {

    public static void main(String[] args) {
        new CanConstruct().canConstruct3("a","b");
    }

    /**
     * 思路一：哈希表
     * 首先建立哈希表map<字符，个数>统计赎金信中所有字符及其个数，然后再遍历杂志magazine中的字符，
     * 每遍历到一个map中的字符，则将对应个数减1，若减到了0，则将此项从map中移除。若哈希表为空了，则说明所有字符都已找到，返回true，否则最后遍历完毕后返回false
     * 此种方法则可能无需遍历完magazine
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> ransomMap = new HashMap<>();
        for(int i = 0;i < ransomNote.length();i++) {
            int num = ransomMap.getOrDefault(ransomNote.charAt(i), 0);
            ransomMap.put(ransomNote.charAt(i), ++num);
        }
        for(int j = 0;j < magazine.length();j++) {
            char c = magazine.charAt(j);
            int num = ransomMap.getOrDefault(c, 0);
            if(num > 0) {
                num--;
                if(num == 0) {
                    ransomMap.remove(c);
                    if(ransomMap.isEmpty()) return true;
                } else {
                    ransomMap.put(c, num);
                }
            }
        }
        return false;
    }

    /**
     * 思路二：字符表
     * 由于题目说明magazine和ransomNote都由小写字母组成，故可使用一个26长度的int数组来统计ransomNote中a-z字符种类数及其个数
     * 然后再遍历magazine中的字符，若满足数组中每种字符的个数，则返回true，否则最后返回false
     */
    public boolean canConstruct2(String ransomNote, String magazine) {
        int[] charTable = new int[26];
        int count = 0;
        //统计ransomNote中字符种类数count以及每种字符的个数
        for(int i = 0;i < ransomNote.length();i++) {
            if (charTable[ransomNote.charAt(i) - 'a']++ == 0) {
                count++;
            }
        }
        //遍历magazine，每遍历到ransomNote中的字符，就将字符数组中对应的字符量减1，若减到了0，则count减1，若count减到了0，则所有字符都已满足，返回true
        for(int j = 0;j < magazine.length();j++) {
            if (charTable[magazine.charAt(j) - 'a'] > 0) {
                int charNum = --charTable[magazine.charAt(j) - 'a'];
                if (charNum == 0) {
                    if (--count == 0) return true;
                }
            }
        }
        //若magazine遍历完了count还没有归零，说明不满足，返回false
        return false;
    }


    public boolean canConstruct3(String ransomNote, String magazine) {
        int[] charTable = new int[26];
        for(int i = 0;i < magazine.length();i++) {
            charTable[magazine.charAt(i) - 'a']++;
        }
        for(int j = 0;j < ransomNote.length();j++) {
            if(--charTable[ransomNote.charAt(j) - 'a'] < 0) return false;
        }
        return true;
    }
}
